SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Baum–Welch algorithm</title>

</head>

Baum–Welch algorithm

</h1>

</header>

In <a href="Electrical_engineering" title="Electrical engineering">electrical engineering</a>, <a href="Statistical_computing" class="mw-redirect" title="Statistical computing">statistical computing</a> and <a href="Bioinformatics" title="Bioinformatics">bioinformatics</a>, the Baum–Welch algorithm is a special case of the <a href="Expectation%E2%80%93maximization_algorithm" title="Expectation–maximization algorithm">expectation–maximization algorithm</a> used to find the unknown parameters of a <a href="Hidden_Markov_model" title="Hidden Markov model">hidden Markov model</a> (HMM). It makes use of the <a href="Forward-backward_algorithm" class="mw-redirect" title="Forward-backward algorithm">forward-backward algorithm</a> to compute the statistics for the expectation step. The Baum–Welch algorithm, the primary method for inference in hidden Markov models, is numerically unstable due to its recursive calculation of joint probabilities. As the number of variables grows, these joint probabilities become increasingly small, leading to the forward recursions rapidly approaching values below machine precision.<a href="#cite_note-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

The Baum–Welch algorithm was named after its inventors <a href="Leonard_E._Baum" title="Leonard E. Baum">Leonard E. Baum</a> and <a href="Lloyd_R._Welch" title="Lloyd R. Welch">Lloyd R. Welch</a>. The algorithm and the Hidden Markov models were first described in a series of articles by Baum and his peers at the <a href="Institute_for_Defense_Analyses#Center_for_Communications_and_Computing" title="Institute for Defense Analyses">IDA Center for Communications Research, Princeton</a> in the late 1960s and early 1970s.<a href="#cite_note-2">[2]</a> One of the first major applications of HMMs was to the field of <a href="Speech_processing" title="Speech processing">speech processing</a>.<a href="#cite_note-3">[3]</a> In the 1980s, HMMs were emerging as a useful tool in the analysis of biological systems and information, and in particular <a href="Genomics" title="Genomics">genetic information</a>.<a href="#cite_note-4">[4]</a> They have since become an important tool in the probabilistic modeling of genomic sequences.<a href="#cite_note-Durbin1998-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Description">Description</h2></div>

A <a href="Hidden_Markov_model" title="Hidden Markov model">hidden Markov model</a> describes the joint probability of a collection of "<a href="Latent_variable" class="mw-redirect" title="Latent variable">hidden</a>" and observed discrete random variables. It relies on the assumption that the i-th hidden variable given the (i − 1)-th hidden variable is independent of previous hidden variables, and the current observation variables depend only on the current hidden state.

The Baum–Welch algorithm uses the well known EM algorithm to find the <a href="Maximum_likelihood" class="mw-redirect" title="Maximum likelihood">maximum likelihood</a> estimate of the parameters of a hidden Markov model given a set of observed feature vectors.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{t}}</annotation>

</semantics>

</math><img src="./82120d04dfb3cbadc4912951dd12b5568c9cd8f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.75ex; height:2.509ex;" alt="{\displaystyle X_{t}}" loading="lazy"> be a discrete hidden random variable with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> possible values (i.e. We assume there are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> states in total). We assume the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(X_{t}\mid X_{t-1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(X_{t}\mid X_{t-1})}</annotation>

</semantics>

</math><img src="./8c378a675bfebb0fb18304254782228d322f06f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.093ex; height:2.843ex;" alt="{\displaystyle P(X_{t}\mid X_{t-1})}" loading="lazy"> is independent of time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">, which leads to the definition of the time-independent stochastic transition matrix

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A=\{a_{ij}\}=P(X_{t}=j\mid X_{t-1}=i).}</annotation>

</semantics>

</math><img src="./ff6e859078a320d5d1ace9a31943457cca5422c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:34.669ex; height:3.009ex;" alt="{\displaystyle A=\{a_{ij}\}=P(X_{t}=j\mid X_{t-1}=i).}" loading="lazy"></dd></dl>

The initial state distribution (i.e. when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=1}</annotation>

</semantics>

</math><img src="./970dea4a5f5ec5355c4cdd62f6396fbc8b1baaa1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.101ex; height:2.176ex;" alt="{\displaystyle t=1}" loading="lazy">) is given by

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi _{i}=P(X_{1}=i).}</annotation>

</semantics>

</math><img src="./0c08955d9009f4560f9064fc0e10bfd6102e2a83.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.304ex; height:2.843ex;" alt="{\displaystyle \pi _{i}=P(X_{1}=i).}" loading="lazy"></dd></dl>

The observation variables <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{t}}</annotation>

</semantics>

</math><img src="./95734a78eb8407939c3496cbfd92763ced1e41e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.177ex; height:2.509ex;" alt="{\displaystyle Y_{t}}" loading="lazy"> can take one of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> possible values. We also assume the observation given the "hidden" state is time independent. The probability of a certain observation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}}</annotation>

</semantics>

</math><img src="./67d30d30b6c2dbe4d6f150d699de040937ecc95f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.939ex; height:2.009ex;" alt="{\displaystyle y_{i}}" loading="lazy"> at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> for state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{t}=j}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{t}=j}</annotation>

</semantics>

</math><img src="./d20b1984afd816992b0368330b1ee60f792c1c7b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.807ex; height:2.509ex;" alt="{\displaystyle X_{t}=j}" loading="lazy"> is given by

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{j}(y_{i})=P(Y_{t}=y_{i}\mid X_{t}=j).}</annotation>

</semantics>

</math><img src="./68c9c3f43bdd27268eaef5569c982ecd496f840f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:28.913ex; height:3.009ex;" alt="{\displaystyle b_{j}(y_{i})=P(Y_{t}=y_{i}\mid X_{t}=j).}" loading="lazy"></dd></dl>

Taking into account all the possible values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{t}}</annotation>

</semantics>

</math><img src="./95734a78eb8407939c3496cbfd92763ced1e41e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.177ex; height:2.509ex;" alt="{\displaystyle Y_{t}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X_{t}}</annotation>

</semantics>

</math><img src="./82120d04dfb3cbadc4912951dd12b5568c9cd8f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.75ex; height:2.509ex;" alt="{\displaystyle X_{t}}" loading="lazy">, we obtain the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\times K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N\times K}</annotation>

</semantics>

</math><img src="./692cb398d63137323f74813a38fafa8e4035ebf4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.97ex; height:2.176ex;" alt="{\displaystyle N\times K}" loading="lazy"> matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B=\{b_{j}(y_{i})\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B=\{b_{j}(y_{i})\}}</annotation>

</semantics>

</math><img src="./b2add6afb915aed6aa6b24ca1edefca4a39f3119.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:12.843ex; height:3.009ex;" alt="{\displaystyle B=\{b_{j}(y_{i})\}}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{j}}</annotation>

</semantics>

</math><img src="./fa56eff4488494085785b7b0d6e2069bd45a3ce5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.907ex; height:2.843ex;" alt="{\displaystyle b_{j}}" loading="lazy"> belongs to all the possible states and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}}</annotation>

</semantics>

</math><img src="./67d30d30b6c2dbe4d6f150d699de040937ecc95f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.939ex; height:2.009ex;" alt="{\displaystyle y_{i}}" loading="lazy"> belongs to all the observations.

An observation sequence is given by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y=(Y_{1}=y_{1},Y_{2}=y_{2},\ldots ,Y_{T}=y_{T})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y=(Y_{1}=y_{1},Y_{2}=y_{2},\ldots ,Y_{T}=y_{T})}</annotation>

</semantics>

</math><img src="./f7d848b32be0358d596abfb66d6c93fc2eee4d83.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.654ex; height:2.843ex;" alt="{\displaystyle Y=(Y_{1}=y_{1},Y_{2}=y_{2},\ldots ,Y_{T}=y_{T})}" loading="lazy">.

Thus we can describe a hidden Markov chain by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta =(A,B,\pi )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta =(A,B,\pi )}</annotation>

</semantics>

</math><img src="./75b1a8e8f935cdc3423ffe31b0f724c5277b28ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.905ex; height:2.843ex;" alt="{\displaystyle \theta =(A,B,\pi )}" loading="lazy">. The Baum–Welch algorithm finds a local maximum for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta ^{*}=\operatorname {arg\,max} _{\theta }P(Y\mid \theta )}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta ^{*}=\operatorname {arg\,max} _{\theta }P(Y\mid \theta )}</annotation>

</semantics>

</math><img src="./a1a6905684f607d7f18eb70e7ebe8ed7afcfe8c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.939ex; height:2.843ex;" alt="{\displaystyle \theta ^{*}=\operatorname {arg\,max} _{\theta }P(Y\mid \theta )}" loading="lazy"> (i.e. the HMM parameters <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> that maximize the probability of the observation).<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading3"><h3 id="Algorithm">Algorithm</h3></div>

Set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta =(A,B,\pi )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta =(A,B,\pi )}</annotation>

</semantics>

</math><img src="./75b1a8e8f935cdc3423ffe31b0f724c5277b28ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.905ex; height:2.843ex;" alt="{\displaystyle \theta =(A,B,\pi )}" loading="lazy"> with random initial conditions. They can also be set using prior information about the parameters if it is available; this can speed up the algorithm and also steer it toward the desired local maximum.

<div class="mw-heading mw-heading4"><h4 id="Forward_procedure">Forward procedure</h4></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{i}(t)=P(Y_{1}=y_{1},\ldots ,Y_{t}=y_{t},X_{t}=i\mid \theta )}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{i}(t)=P(Y_{1}=y_{1},\ldots ,Y_{t}=y_{t},X_{t}=i\mid \theta )}</annotation>

</semantics>

</math><img src="./1c382298c0f6420ce2f301367d0df5093c597f38.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.417ex; height:2.843ex;" alt="{\displaystyle \alpha _{i}(t)=P(Y_{1}=y_{1},\ldots ,Y_{t}=y_{t},X_{t}=i\mid \theta )}" loading="lazy">, the probability of seeing the observations <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1},y_{2},\ldots ,y_{t}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1},y_{2},\ldots ,y_{t}}</annotation>

</semantics>

</math><img src="./1d4ec04f411ee317535d6ff3a03f0011798d1ae7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.564ex; height:2.009ex;" alt="{\displaystyle y_{1},y_{2},\ldots ,y_{t}}" loading="lazy"> and being in state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">. This is found recursively:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{i}(1)=\pi _{i}b_{i}(y_{1}),}</annotation>

</semantics>

</math><img src="./c174ae8776db016c43587bfd3b18745a343d6a65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.929ex; height:2.843ex;" alt="{\displaystyle \alpha _{i}(1)=\pi _{i}b_{i}(y_{1}),}" loading="lazy"></li>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha _{i}(t+1)=b_{i}(y_{t+1})\sum _{j=1}^{N}\alpha _{j}(t)a_{ji}.}</annotation>

</semantics>

</math><img src="./4c8bfa2ed738c25d21e181e8b6acef51e65dc9a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:32.239ex; height:7.676ex;" alt="{\displaystyle \alpha _{i}(t+1)=b_{i}(y_{t+1})\sum _{j=1}^{N}\alpha _{j}(t)a_{ji}.}" loading="lazy"></li></ol>

Since this series converges exponentially to zero, the algorithm will numerically underflow for longer sequences.<a href="#cite_note-7">[7]</a> However, this can be avoided in a slightly modified algorithm by scaling <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"> in the forward and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta }</annotation>

</semantics>

</math><img src="./7ed48a5e36207156fb792fa79d29925d2f7901e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.332ex; height:2.509ex;" alt="{\displaystyle \beta }" loading="lazy"> in the backward procedure below.

<div class="mw-heading mw-heading4"><h4 id="Backward_procedure">Backward procedure</h4></div>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta _{i}(t)=P(Y_{t+1}=y_{t+1},\ldots ,Y_{T}=y_{T}\mid X_{t}=i,\theta )}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta _{i}(t)=P(Y_{t+1}=y_{t+1},\ldots ,Y_{T}=y_{T}\mid X_{t}=i,\theta )}</annotation>

</semantics>

</math><img src="./59692a43bb31545c990107b9e7a328f1c0d1f923.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:47.117ex; height:2.843ex;" alt="{\displaystyle \beta _{i}(t)=P(Y_{t+1}=y_{t+1},\ldots ,Y_{T}=y_{T}\mid X_{t}=i,\theta )}" loading="lazy"> that is the probability of the ending partial sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{t+1},\ldots ,y_{T}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{t+1},\ldots ,y_{T}}</annotation>

</semantics>

</math><img src="./49fbda54a69e96c7afd17dad040b8e2f28253ace.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.772ex; height:2.009ex;" alt="{\displaystyle y_{t+1},\ldots ,y_{T}}" loading="lazy"> given starting state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">. We calculate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \beta _{i}(t)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta _{i}(t)}</annotation>

</semantics>

</math><img src="./897ff67b67a66430326fd288670e3c3ac3c85b73.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.764ex; height:2.843ex;" alt="{\displaystyle \beta _{i}(t)}" loading="lazy"> as,

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta _{i}(T)=1,}</annotation>

</semantics>

</math><img src="./59d75f55e3c61a4eb97eee7cd392e43f0e28a643.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.469ex; height:2.843ex;" alt="{\displaystyle \beta _{i}(T)=1,}" loading="lazy"></li>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta _{i}(t)=\sum _{j=1}^{N}\beta _{j}(t+1)a_{ij}b_{j}(y_{t+1}).}</annotation>

</semantics>

</math><img src="./253927c954011820ef9f0aab3bc6e8bf0529f61b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:31.618ex; height:7.676ex;" alt="{\displaystyle \beta _{i}(t)=\sum _{j=1}^{N}\beta _{j}(t+1)a_{ij}b_{j}(y_{t+1}).}" loading="lazy"></li></ol>

<div class="mw-heading mw-heading4"><h4 id="Update">Update</h4></div>

We can now calculate the temporary variables, according to Bayes' theorem:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma _{i}(t)=P(X_{t}=i\mid Y,\theta )={\frac {P(X_{t}=i,Y\mid \theta )}{P(Y\mid \theta )}}={\frac {\alpha _{i}(t)\beta _{i}(t)}{\sum _{j=1}^{N}\alpha _{j}(t)\beta _{j}(t)}},}</annotation>

</semantics>

</math><img src="./edc48162179b71aefcdedef634c8aaae8881d8d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:64.121ex; height:7.343ex;" alt="{\displaystyle \gamma _{i}(t)=P(X_{t}=i\mid Y,\theta )={\frac {P(X_{t}=i,Y\mid \theta )}{P(Y\mid \theta )}}={\frac {\alpha _{i}(t)\beta _{i}(t)}{\sum _{j=1}^{N}\alpha _{j}(t)\beta _{j}(t)}},}" loading="lazy"></dd></dl>

which is the probability of being in state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> given the observed sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> and the parameters <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{ij}(t)=P(X_{t}=i,X_{t+1}=j\mid Y,\theta )={\frac {P(X_{t}=i,X_{t+1}=j,Y\mid \theta )}{P(Y\mid \theta )}}={\frac {\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})}{\sum _{k=1}^{N}\sum _{w=1}^{N}\alpha _{k}(t)a_{kw}\beta _{w}(t+1)b_{w}(y_{t+1})}},}</annotation>

</semantics>

</math><img src="./9b3b980e01c26b6864065d79cb731796fd71eec1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:107.482ex; height:7.009ex;" alt="{\displaystyle \xi _{ij}(t)=P(X_{t}=i,X_{t+1}=j\mid Y,\theta )={\frac {P(X_{t}=i,X_{t+1}=j,Y\mid \theta )}{P(Y\mid \theta )}}={\frac {\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})}{\sum _{k=1}^{N}\sum _{w=1}^{N}\alpha _{k}(t)a_{kw}\beta _{w}(t+1)b_{w}(y_{t+1})}},}" loading="lazy"></dd></dl>

which is the probability of being in state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> at times <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t+1}</annotation>

</semantics>

</math><img src="./ab2785d8415d6902b0c93efe1419c4bc3ce4643d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.842ex; height:2.343ex;" alt="{\displaystyle t+1}" loading="lazy"> respectively given the observed sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> and parameters <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy">.

The denominators of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma _{i}(t)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma _{i}(t)}</annotation>

</semantics>

</math><img src="./330703b1e387eed98ead89890dfae622fc26d991.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.653ex; height:2.843ex;" alt="{\displaystyle \gamma _{i}(t)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{ij}(t)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{ij}(t)}</annotation>

</semantics>

</math><img src="./f379cf0e5eea7ae6f388b2a8974f685834c64eca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.145ex; height:3.009ex;" alt="{\displaystyle \xi _{ij}(t)}" loading="lazy"> are the same ; they represent the probability of making the observation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> given the parameters <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy">.

The parameters of the hidden Markov model <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta }</annotation>

</semantics>

</math><img src="./6e5ab2664b422d53eb0c7df3b87e1360d75ad9af.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:2.176ex;" alt="{\displaystyle \theta }" loading="lazy"> can now be updated:

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi _{i}^{*}=\gamma _{i}(1),}</annotation>

</semantics>

</math><img src="./4473f2856293081692fd1b786f8af92b249076aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.109ex; height:3.009ex;" alt="{\displaystyle \pi _{i}^{*}=\gamma _{i}(1),}" loading="lazy"></li></ul>

which is the expected frequency spent in state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> at time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">.

</mrow>

</mrow>

</msubsup>

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{ij}^{*}={\frac {\sum _{t=1}^{T-1}\xi _{ij}(t)}{\sum _{t=1}^{T-1}\gamma _{i}(t)}},}</annotation>

</semantics>

</math><img src="./5c65e4b98b0796692e8227702fec4e62d6525e02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:18.764ex; height:7.509ex;" alt="{\displaystyle a_{ij}^{*}={\frac {\sum _{t=1}^{T-1}\xi _{ij}(t)}{\sum _{t=1}^{T-1}\gamma _{i}(t)}},}" loading="lazy"></li></ul>

which is the expected number of transitions from state i to state j compared to the expected total number of transitions starting in state i, including from state i to itself. The number of transitions starting in state i is equivalent to the number of times state i is observed in the sequence from t = 1 to t = T − 1.

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}^{*}(v_{k})={\frac {\sum _{t=1}^{T}1_{y_{t}=v_{k}}\gamma _{i}(t)}{\sum _{t=1}^{T}\gamma _{i}(t)}},}</annotation>

</semantics>

</math><img src="./eef4f2a348673bcb6cb7cd545b84e451898cb7bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:26.861ex; height:7.676ex;" alt="{\displaystyle b_{i}^{*}(v_{k})={\frac {\sum _{t=1}^{T}1_{y_{t}=v_{k}}\gamma _{i}(t)}{\sum _{t=1}^{T}\gamma _{i}(t)}},}" loading="lazy"></li></ul>

where

<msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>otherwise</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1_{y_{t}=v_{k}}={\begin{cases}1&{\text{if }}y_{t}=v_{k},\\0&{\text{otherwise}}\end{cases}}}</annotation>

</semantics>

</math><img src="./4962e05fdbf3d25416957eac858c569f62a1940c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:24.726ex; height:6.176ex;" alt="{\displaystyle 1_{y_{t}=v_{k}}={\begin{cases}1&{\text{if }}y_{t}=v_{k},\\0&{\text{otherwise}}\end{cases}}}" loading="lazy"></dd></dl>

is an indicator function, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{i}^{*}(v_{k})}">

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}^{*}(v_{k})}</annotation>

</semantics>

</math><img src="./2befa2379401d81fdfe78a7277c8a9f7a196924a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.077ex; height:3.009ex;" alt="{\displaystyle b_{i}^{*}(v_{k})}" loading="lazy"> is the expected number of times the output observations have been equal to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{k}}</annotation>

</semantics>

</math><img src="./d142b4083872eb72f81c1e20fd2c91d02b4a9838.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.216ex; height:2.009ex;" alt="{\displaystyle v_{k}}" loading="lazy"> while in state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> over the expected total number of times in state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">.

These steps are now repeated iteratively until a desired level of convergence.

Note: It is possible to over-fit a particular data set. That is, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(Y\mid \theta _{\text{final}})>P(Y\mid \theta _{\text{true}})}">

<msub>

<mtext>final</mtext>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(Y\mid \theta _{\text{final}})>P(Y\mid \theta _{\text{true}})}</annotation>

</semantics>

</math><img src="./3295efae4b98a08b85848e0105f8001d60abe8ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.357ex; height:2.843ex;" alt="{\displaystyle P(Y\mid \theta _{\text{final}})>P(Y\mid \theta _{\text{true}})}" loading="lazy">. The algorithm also does not guarantee a global maximum.

<div class="mw-heading mw-heading4"><h4 id="Multiple_sequences">Multiple sequences</h4></div>

The algorithm described thus far assumes a single observed sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y=y_{1},\ldots ,y_{T}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y=y_{1},\ldots ,y_{T}}</annotation>

</semantics>

</math><img src="./47c9dd93d90a77b688b75699f54428fbfcefeb31.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.772ex; height:2.509ex;" alt="{\displaystyle Y=y_{1},\ldots ,y_{T}}" loading="lazy">. However, in many situations, there are several sequences observed: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y_{1},\ldots ,Y_{R}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y_{1},\ldots ,Y_{R}}</annotation>

</semantics>

</math><img src="./15afbc55adff19c8966f12b8dce22d10ac462b5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.413ex; height:2.509ex;" alt="{\displaystyle Y_{1},\ldots ,Y_{R}}" loading="lazy">. In this case, the information from all of the observed sequences must be used in the update of the parameters <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi }</annotation>

</semantics>

</math><img src="./9be4ba0bb8df3af72e90a0535fabcc17431e540a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy">. Assuming that you have computed <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma _{ir}(t)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma _{ir}(t)}</annotation>

</semantics>

</math><img src="./e3229095e35f656da32cd8649ca93bf494d5c425.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.394ex; height:2.843ex;" alt="{\displaystyle \gamma _{ir}(t)}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \xi _{ijr}(t)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \xi _{ijr}(t)}</annotation>

</semantics>

</math><img src="./ac750d74deb654ce30f1edbda1116a3fcd6a5253.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.886ex; height:3.009ex;" alt="{\displaystyle \xi _{ijr}(t)}" loading="lazy"> for each sequence <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1,r},\ldots ,y_{N_{r},r}}">

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1,r},\ldots ,y_{N_{r},r}}</annotation>

</semantics>

</math><img src="./bb4fe26bb83cba87b54ef6b439479b9f793b02de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.227ex; height:2.343ex;" alt="{\displaystyle y_{1,r},\ldots ,y_{N_{r},r}}" loading="lazy">, the parameters can now be updated:

</mrow>

</mrow>

</msubsup>

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi _{i}^{*}={\frac {\sum _{r=1}^{R}\gamma _{ir}(1)}{R}}}</annotation>

</semantics>

</math><img src="./d7c73c15f7cb2ce848c5dda50d70ca82a78ef53c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:17.955ex; height:6.343ex;" alt="{\displaystyle \pi _{i}^{*}={\frac {\sum _{r=1}^{R}\gamma _{ir}(1)}{R}}}" loading="lazy"></li>

</mrow>

</mrow>

</msubsup>

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{ij}^{*}={\frac {\sum _{r=1}^{R}\sum _{t=1}^{T-1}\xi _{ijr}(t)}{\sum _{r=1}^{R}\sum _{t=1}^{T-1}\gamma _{ir}(t)}},}</annotation>

</semantics>

</math><img src="./fdd0f93163ff1b47b311128da728757c64757bf7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:25.42ex; height:7.509ex;" alt="{\displaystyle a_{ij}^{*}={\frac {\sum _{r=1}^{R}\sum _{t=1}^{T-1}\xi _{ijr}(t)}{\sum _{r=1}^{R}\sum _{t=1}^{T-1}\gamma _{ir}(t)}},}" loading="lazy"></li>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}^{*}(v_{k})={\frac {\sum _{r=1}^{R}\sum _{t=1}^{T}1_{y_{tr}=v_{k}}\gamma _{ir}(t)}{\sum _{r=1}^{R}\sum _{t=1}^{T}\gamma _{ir}(t)}},}</annotation>

</semantics>

</math><img src="./c1c2f768973414c0196dc56b73121519f35c4cae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:34.12ex; height:7.676ex;" alt="{\displaystyle b_{i}^{*}(v_{k})={\frac {\sum _{r=1}^{R}\sum _{t=1}^{T}1_{y_{tr}=v_{k}}\gamma _{ir}(t)}{\sum _{r=1}^{R}\sum _{t=1}^{T}\gamma _{ir}(t)}},}" loading="lazy"></li></ul>

where

<msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>otherwise</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1_{y_{tr}=v_{k}}={\begin{cases}1&{\text{if }}y_{t,r}=v_{k},\\0&{\text{otherwise}}\end{cases}}}</annotation>

</semantics>

</math><img src="./8ce9c4f814a0ac6baa1a6e9aa2d02af8edf0aa17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:26.527ex; height:6.176ex;" alt="{\displaystyle 1_{y_{tr}=v_{k}}={\begin{cases}1&{\text{if }}y_{t,r}=v_{k},\\0&{\text{otherwise}}\end{cases}}}" loading="lazy"></dd></dl>

is an indicator function

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

Suppose we have a chicken from which we collect eggs at noon every day. Now whether or not the chicken has laid eggs for collection depends on some unknown factors that are hidden. We can however (for simplicity) assume that the chicken is always in one of two states that influence whether the chicken lays eggs, and that this state only depends on the state on the previous day. Now we don't know the state at the initial starting point, we don't know the transition probabilities between the two states and we don't know the probability that the chicken lays an egg given a particular state.<a href="#cite_note-8">[8]</a><a href="#cite_note-9">[9]</a> To start we first guess the transition and emission matrices.

<td>

<caption>Transition

</caption>

<th>State 1</th>

<th>State 2

</th></tr>

<tr>

<th>State 1

</th>

<td>0.5

</td></tr>

<tr>

<th>State 2

</th>

<td>0.7

</td></tr></tbody></table>

</td>

<td>

<caption>Emission

</caption>

<th>Eggs

</th></tr>

<tr>

<th>State 1

</th>

<td>0.7

</td></tr>

<tr>

<th>State 2

</th>

<td>0.2

</td></tr></tbody></table>

</td>

<td>

<caption>Initial

</caption>

<th>State 1

</th>

<td>0.2

</td></tr>

<tr>

<th>State 2

</th>

<td>0.8

</td></tr></tbody></table>

We then take a set of observations (E = eggs, N = no eggs): N, N, N, N, N, E, E, N, N, N

This gives us a set of observed transitions between days: NN, NN, NN, NN, NE, EE, EN, NN, NN

The next step is to estimate a new transition matrix. For example, the probability of the sequence NN and the state being ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠ then ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠ is given by the following,

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(S_{1})\cdot P(N|S_{1})\cdot P(S_{1}\rightarrow S_{2})\cdot P(N|S_{2}).}</annotation>

</semantics>

</math><img src="./773e7fc082ea381254d525d713141eb95816d967.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:41.334ex; height:2.843ex;" alt="{\displaystyle P(S_{1})\cdot P(N|S_{1})\cdot P(S_{1}\rightarrow S_{2})\cdot P(N|S_{2}).}" loading="lazy">

<th>Observed sequence</th>

<th>Highest probability of observing that sequence if state is ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠ then ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠</th>

<th colspan="2">Highest Probability of observing that sequence

</th></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠

</td></tr>

<tr>

<th>Total

</th>

<td>

</td></tr></tbody></table>

Thus the new estimate for the ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠ to ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠ transition is now <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {0.22}{2.4234}}=0.0908}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {0.22}{2.4234}}=0.0908}</annotation>

</semantics>

</math><img src="./399cbb3ce8c27203ef165fc50e4c4cd4a50ea43a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:16.853ex; height:5.343ex;" alt="{\displaystyle {\frac {0.22}{2.4234}}=0.0908}" loading="lazy"> (referred to as "Pseudo probabilities" in the following tables). We then calculate the ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠ to ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠, ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠ to ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠ and ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠ to ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠ transition probabilities and normalize so they add to 1. This gives us the updated transition matrix:

<td>

<caption>Old Transition Matrix

</caption>

<th>State 1</th>

<th>State 2

</th></tr>

<tr>

<th>State 1

</th>

<td>0.5

</td></tr>

<tr>

<th>State 2

</th>

<td>0.7

</td></tr></tbody></table>

</td>

<td>

<caption>New Transition Matrix (Pseudo Probabilities)

</caption>

<th>State 1</th>

<th>State 2

</th></tr>

<tr>

<th>State 1

</th>

<td>0.0908

</td></tr>

<tr>

<th>State 2

</th>

<td>0.9705

</td></tr></tbody></table>

</td>

<td>

<caption>New Transition Matrix (After Normalization)

</caption>

<th>State 1</th>

<th>State 2

</th></tr>

<tr>

<th>State 1

</th>

<td>0.6027

</td></tr>

<tr>

<th>State 2

</th>

<td>0.8167

</td></tr></tbody></table>

Next, we want to estimate a new emission matrix,

<th>Observed Sequence</th>

<th colspan="2">Highest probability of observing that sequence if E is assumed to come from ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠</th>

<th colspan="2">Highest Probability of observing that sequence

</th></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠</td>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠</td>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠

</td></tr>

<tr>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠</td>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠,⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠

</td></tr>

<tr>

<th>Total

</th>

<td>

</td></tr></tbody></table>

The new estimate for the E coming from ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠ emission is now <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {0.2394}{0.2730}}=0.8769}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {0.2394}{0.2730}}=0.8769}</annotation>

</semantics>

</math><img src="./a5770523e36bf494ec78eeacdd03c5810ebfb102.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:16.853ex; height:5.343ex;" alt="{\displaystyle {\frac {0.2394}{0.2730}}=0.8769}" loading="lazy">.

This allows us to calculate the emission matrix as described above in the algorithm, by adding up the probabilities for the respective observed sequences. We then repeat for if N came from ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠ and for if N and E came from ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠ and normalize.

<td>

<caption>Old Emission Matrix

</caption>

<th>Eggs

</th></tr>

<tr>

<th>State 1

</th>

<td>0.7

</td></tr>

<tr>

<th>State 2

</th>

<td>0.2

</td></tr></tbody></table>

</td>

<td>

<caption>New Emission Matrix (Estimates)

</caption>

<th>Eggs

</th></tr>

<tr>

<th>State 1

</th>

<td>0.8769

</td></tr>

<tr>

<th>State 2

</th>

<td>0.7385

</td></tr></tbody></table>

</td>

<td>

<caption>New Emission Matrix (After Normalization)

</caption>

<th>Eggs

</th></tr>

<tr>

<th>State 1

</th>

<td>0.9559

</td></tr>

<tr>

<th>State 2

</th>

<td>0.4248

</td></tr></tbody></table>

To estimate the initial probabilities we assume all sequences start with the hidden state ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy">⁠ and calculate the highest probability and then repeat for ⁠<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy">⁠. Again we then normalize to give an updated initial vector.

Finally we repeat these steps until the resulting probabilities converge satisfactorily.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Speech_recognition">Speech recognition</h3></div>

Hidden Markov Models were first applied to speech recognition by <a href="James_K._Baker" title="James K. Baker">James K. Baker</a> in 1975.<a href="#cite_note-10">[10]</a> Continuous speech recognition occurs by the following steps, modeled by a HMM. Feature analysis is first undertaken on temporal and/or spectral features of the speech signal. This produces an observation vector. The feature is then compared to all sequences of the speech recognition units. These units could be <a href="Phonemes" class="mw-redirect" title="Phonemes">phonemes</a>, syllables, or whole-word units. A lexicon decoding system is applied to constrain the paths investigated, so only words in the system's lexicon (word dictionary) are investigated. Similar to the lexicon decoding, the system path is further constrained by the rules of grammar and syntax. Finally, semantic analysis is applied and the system outputs the recognized utterance. A limitation of many HMM applications to speech recognition is that the current state only depends on the state at the previous time-step, which is unrealistic for speech as dependencies are often several time-steps in duration.<a href="#cite_note-11">[11]</a> The Baum–Welch algorithm also has extensive applications in solving HMMs used in the field of speech synthesis.<a href="#cite_note-12">[12]</a>

<div class="mw-heading mw-heading3"><h3 id="Cryptanalysis">Cryptanalysis</h3></div>

The Baum–Welch algorithm is often used to estimate the parameters of HMMs in deciphering hidden or noisy information and consequently is often used in <a href="Cryptanalysis" title="Cryptanalysis">cryptanalysis</a>. In data security an observer would like to extract information from a data stream without knowing all the parameters of the transmission. This can involve reverse engineering a <a href="Coding_theory" title="Coding theory">channel encoder</a>.<a href="#cite_note-13">[13]</a> HMMs and as a consequence the Baum–Welch algorithm have also been used to identify spoken phrases in encrypted VoIP calls.<a href="#cite_note-14">[14]</a> In addition HMM cryptanalysis is an important tool for automated investigations of cache-timing data. It allows for the automatic discovery of critical algorithm state, for example key values.<a href="#cite_note-15">[15]</a>

<div class="mw-heading mw-heading3"><h3 id="Applications_in_bioinformatics">Applications in bioinformatics</h3></div>

<div class="mw-heading mw-heading4"><h4 id="Finding_genes">Finding genes</h4></div>

<div class="mw-heading mw-heading5"><h5 id="Prokaryotic">Prokaryotic</h5></div>

The <a href="GLIMMER" title="GLIMMER">GLIMMER</a> (Gene Locator and Interpolated Markov ModelER) software was an early <a href="Locus_(genetics)" title="Locus (genetics)">gene-finding</a> program used for the identification of coding regions in <a href="Prokaryotic" class="mw-redirect" title="Prokaryotic">prokaryotic</a> DNA.<a href="#cite_note-GLIMMER_paper-16">[16]</a><a href="#cite_note-GLIMMER_web-17">[17]</a> GLIMMER uses Interpolated Markov Models (IMMs) to identify the <a href="Exon" title="Exon">coding regions</a> and distinguish them from the <a href="Introns" class="mw-redirect" title="Introns">noncoding DNA</a>. The latest release (GLIMMER3) has been shown to have increased <a href="Specificity_(statistics)" class="mw-redirect" title="Specificity (statistics)">specificity</a> and accuracy compared with its predecessors with regard to predicting translation initiation sites, demonstrating an average 99% accuracy in locating 3' locations compared to confirmed genes in prokaryotes.<a href="#cite_note-18">[18]</a>

<div class="mw-heading mw-heading5"><h5 id="Eukaryotic">Eukaryotic</h5></div>

The <a href="GENSCAN" title="GENSCAN">GENSCAN</a> webserver is a gene locator capable of analyzing <a href="Eukaryotic" class="mw-redirect" title="Eukaryotic">eukaryotic</a> sequences up to one million base-pairs (1 Mbp) long.<a href="#cite_note-19">[19]</a> GENSCAN utilizes a general inhomogeneous, three periodic, fifth order Markov model of DNA coding regions. Additionally, this model accounts for differences in gene density and structure (such as intron lengths) that occur in different <a href="Isochore_(genetics)" title="Isochore (genetics)">isochores</a>. While most integrated gene-finding software (at the time of GENSCANs release) assumed input sequences contained exactly one gene, GENSCAN solves a general case where partial, complete, or multiple genes (or even no gene at all) is present.<a href="#cite_note-20">[20]</a> GENSCAN was shown to exactly predict exon location with 90% accuracy with 80% specificity compared to an annotated database.<a href="#cite_note-21">[21]</a>

<div class="mw-heading mw-heading4"><h4 id="Copy-number_variation_detection">Copy-number variation detection</h4></div>

<a href="Copy-number_variation" class="mw-redirect" title="Copy-number variation">Copy-number variations</a> (CNVs) are an abundant form of genome structure variation in humans. A discrete-valued bivariate HMM (dbHMM) was used assigning chromosomal regions to seven distinct states: unaffected regions, deletions, duplications and four transition states. Solving this model using Baum-Welch demonstrated the ability to predict the location of CNV breakpoint to approximately 300 bp from <a href="DNA_microarray" title="DNA microarray">micro-array experiments</a>.<a href="#cite_note-22">[22]</a> This magnitude of resolution enables more precise correlations between different CNVs and <a href="Structural_variations" class="mw-redirect" title="Structural variations">across populations</a> than previously possible, allowing the study of CNV population frequencies. It also demonstrated a <a href="Mendelian_inheritance" title="Mendelian inheritance">direct inheritance pattern for a particular CNV</a>.

<div class="mw-heading mw-heading2"><h2 id="Implementations">Implementations</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://accord-framework.net/docs/html/T_Accord_Statistics_Models_Markov_HiddenMarkovModel.htm">Accord.NET</a> in <a href="C_Sharp_(programming_language)" title="C Sharp (programming language)">C#</a></li>

<li><a rel="nofollow" class="external text" href="http://ghmm.org/">ghmm</a> C library with <a href="Python_(programming_language)" title="Python (programming language)">Python</a> bindings that supports both discrete and continuous emissions.</li>

<li><a rel="nofollow" class="external text" href="https://github.com/hmmlearn/hmmlearn">hmmlearn</a> <a href="Python_(programming_language)" title="Python (programming language)">Python</a> library that implements Baum-Welch on various discrete-time <a href="Hidden_Markov_model" title="Hidden Markov model"> HMMs</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/Rapfff/jajapy">Jajapy</a> <a href="Python_(programming_language)" title="Python (programming language)">Python</a> library that implements Baum-Welch on various kind of Markov Models (<a href="Hidden_Markov_model" title="Hidden Markov model"> HMM</a>, <a href="Markov_chain" title="Markov chain"> MC</a>, <a href="Markov_decision_process" title="Markov decision process">MDP</a>, <a href="Continuous-time_Markov_chain" title="Continuous-time Markov chain"> CTMC</a>).</li>

<li><a rel="nofollow" class="external text" href="https://github.com/gdalle/HiddenMarkovModels.jl">HiddenMarkovModels.jl</a> package for <a href="Julia_(programming_language)" title="Julia (programming language)">Julia</a>.</li>

<li>HMMFit function in the <a rel="nofollow" class="external text" href="https://cran.r-project.org/src/contrib/Archive/RHmm/">RHmm</a> package for <a href="R_(programming_language)" title="R (programming language)">R</a>.</li>

<li><a rel="nofollow" class="external text" href="http://www.mathworks.com.au/help/stats/hmmtrain.html?searchHighlight=baum-welch">hmmtrain</a> in <a href="MATLAB" title="MATLAB">MATLAB</a></li>

<li><a rel="nofollow" class="external text" href="https://docs.rs/bio/0.39.0/bio/stats/hmm/index.html">rustbio</a> in <a href="Rust_(programming_language)" title="Rust (programming language)">Rust</a></li></ul>

<ul><li><a href="Viterbi_algorithm" title="Viterbi algorithm">Viterbi algorithm</a></li>

<li><a href="Hidden_Markov_model" title="Hidden Markov model">Hidden Markov model</a></li>

<li><a href="EM_algorithm" class="mw-redirect" title="EM algorithm">EM algorithm</a></li>

<li><a href="Maximum_likelihood" class="mw-redirect" title="Maximum likelihood">Maximum likelihood</a></li>

<li><a href="Speech_recognition" title="Speech recognition">Speech recognition</a></li>

<li><a href="Bioinformatics" title="Bioinformatics">Bioinformatics</a></li>

<li><a href="Cryptanalysis" title="Cryptanalysis">Cryptanalysis</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://gregorygundersen.com/blog/2022/08/13/hmm-scaling-factors/">"Scaling Factors for Hidden Markov Models"</a>. gregorygundersen.com. Retrieved 2024-10-19.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFRabiner" class="citation web cs1">Rabiner, Lawrence. <a rel="nofollow" class="external text" href="http://www.ieeeghn.org/wiki/index.php/First-Hand:The_Hidden_Markov_Model">"First Hand: The Hidden Markov Model"</a>. IEEE Global History Network. Retrieved 2 October 2013.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFJelinekBahlMercer1975" class="citation journal cs1">Jelinek, Frederick; Bahl, Lalit R.; Mercer, Robert L. (May 1975). "Design of a linguistic statistical decoder for the recognition of continuous speech". IEEE Transactions on Information Theory. 21 (3): 250–6. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftit.1975.1055384">10.1109/tit.1975.1055384</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFBishopThompson1986" class="citation journal cs1">Bishop, Martin J.; Thompson, Elizabeth A. (20 July 1986). "Maximum likelihood alignment of DNA sequences". Journal of Molecular Biology. 190 (2): 159–65. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-2836%2886%2990289-5">10.1016/0022-2836(86)90289-5</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/3641921">3641921</a>.</cite>

</li>

<li id="cite_note-Durbin1998-5"><a href="#cite_ref-Durbin1998_5-0">^</a> <cite id="CITEREFDurbin1998" class="citation book cs1">Durbin, Richard (23 April 1998). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=R5P2GlJvigQC">Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids</a>. Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-62041-3</bdi>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFBilmes1998" class="citation book cs1">Bilmes, Jeff A. (1998). A Gentle Tutorial of the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models. Berkeley, CA: International Computer Science Institute. pp. 7–13.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFRabiner1989" class="citation web cs1">Rabiner, Lawrence (February 1989). <a rel="nofollow" class="external text" href="https://www.ece.ucsb.edu/Faculty/Rabiner/ece259/Reprints/tutorial%20on%20hmm%20and%20applications.pdf">"A Tutorial on Hidden Markov Models and Selected Applications in Speech recognition"</a> (PDF). Proceedings of the IEEE. Retrieved 29 November 2019.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20210414224816/http://www.biostat.jhsph.edu/bstcourse/bio638/notes/HMMs_BaumWelch.pdf">"Baum-Welch and HMM applications"</a> (PDF). Johns Hopkins Bloomberg School of Public Health. Archived from <a rel="nofollow" class="external text" href="http://www.biostat.jhsph.edu/bstcourse/bio638/notes/HMMs_BaumWelch.pdf">the original</a> (PDF) on 2021-04-14. Retrieved 11 October 2019.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFFrazzoli" class="citation web cs1">Frazzoli, Emilio. <a rel="nofollow" class="external text" href="http://ocw.mit.edu/courses/aeronautics-and-astronautics/16-410-principles-of-autonomy-and-decision-making-fall-2010/lecture-notes/MIT16_410F10_lec21.pdf">"Intro to Hidden Markov Models: the Baum-Welch Algorithm"</a> (PDF). Aeronautics and Astronautics, Massachusetts Institute of Technology. Retrieved 2 October 2013.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFBaker1975" class="citation journal cs1"><a href="James_K._Baker" title="James K. Baker">Baker, James K.</a> (1975). "The DRAGON system—An overview". IEEE Transactions on Acoustics, Speech, and Signal Processing. 23: 24–29. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTASSP.1975.1162650">10.1109/TASSP.1975.1162650</a>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFRabiner1989" class="citation journal cs1">Rabiner, Lawrence (February 1989). "A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition". Proceedings of the IEEE. 77 (2): 257–286. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.381.3454">10.1.1.381.3454</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F5.18626">10.1109/5.18626</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13618539">13618539</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFTokudaYoshimuraMasukoKobayashi2000" class="citation journal cs1">Tokuda, Keiichi; Yoshimura, Takayoshi; Masuko, Takashi; Kobayashi, Takao; Kitamura, Tadashi (2000). "Speech Parameter Generation Algorithms for HMM-Based Speech Synthesis". IEEE International Conference on Acoustics, Speech, and Signal Processing. 3.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFDingelHagenauer2007" class="citation journal cs1">Dingel, Janis; Hagenauer, Joachim (24 June 2007). "Parameter Estimation of a Convolutional Encoder from Noisy Observations". IEEE International Symposium on Information Theory.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFWrightBallardCoullMonrose2008" class="citation journal cs1">Wright, Charles; Ballard, Lucas; Coull, Scott; Monrose, Fabian; Masson, Gerald (2008). "Spot me if you can: Uncovering spoken phrases in encrypted VoIP conversations". IEEE International Symposium on Security and Privacy.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFBrumleyHakala2009" class="citation book cs1">Brumley, Bob; Hakala, Risto (2009). "Cache-Timing Template Attacks". Advances in Cryptology – ASIACRYPT 2009. Lecture Notes in Computer Science. Vol. 5912. pp. 667–684. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-10366-7_39">10.1007/978-3-642-10366-7_39</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-10365-0</bdi>.</cite>

</li>

<li id="cite_note-GLIMMER_paper-16"><a href="#cite_ref-GLIMMER_paper_16-0">^</a> <cite id="CITEREFSalzbergDelcherKasifWhite1998" class="citation journal cs1">Salzberg, Steven; Delcher, Arthur L.; Kasif, Simon; White, Owen (1998). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC147303">"Microbial gene identification using interpolated Markov Models"</a>. Nucleic Acids Research. 26 (2): 544–548. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fnar%2F26.2.544">10.1093/nar/26.2.544</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC147303">147303</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/9421513">9421513</a>.</cite>

</li>

<li id="cite_note-GLIMMER_web-17"><a href="#cite_ref-GLIMMER_web_17-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://ccb.jhu.edu/software/glimmer/index.shtml">"Glimmer: Microbial Gene-Finding System"</a>. Johns Hopkins University - Center for Computational Biology.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite id="CITEREFDelcherBratkePowersSalzberg2007" class="citation journal cs1">Delcher, Arthur; Bratke, Kirsten A.; Powers, Edwin C.; Salzberg, Steven L. (2007). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2387122">"Identifying bacterial genes and endosymbiont DNA with Glimmer"</a>. Bioinformatics. 23 (6): 673–679. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fbioinformatics%2Fbtm009">10.1093/bioinformatics/btm009</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2387122">2387122</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/17237039">17237039</a>.</cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFBurge" class="citation web cs1">Burge, Christopher. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20130906115338/http://genes.mit.edu/GENSCAN.html">"The GENSCAN Web Server at MIT"</a>. Archived from <a rel="nofollow" class="external text" href="http://genes.mit.edu/GENSCAN.html">the original</a> on 6 September 2013. Retrieved 2 October 2013.</cite>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFBurgeKarlin1997" class="citation journal cs1">Burge, Chris; Karlin, Samuel (1997). "Prediction of Complete Gene Structures in Human Genomic DNA". Journal of Molecular Biology. 268 (1): 78–94. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.3107">10.1.1.115.3107</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjmbi.1997.0951">10.1006/jmbi.1997.0951</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/9149143">9149143</a>.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFBurgeKarlin1998" class="citation journal cs1">Burge, Christopher; Karlin, Samuel (1998). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0959-440x%2898%2980069-9">"Finding the Genes in Genomic DNA"</a>. Current Opinion in Structural Biology. 8 (3): 346–354. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0959-440x%2898%2980069-9">10.1016/s0959-440x(98)80069-9</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/9666331">9666331</a>.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFKorbelUrbanGrubertDu2007" class="citation journal cs1"><a href="Jan_O._Korbel" title="Jan O. Korbel">Korbel, Jan</a>; Urban, Alexander; Grubert, Fabien; Du, Jiang; Royce, Thomas; Starr, Peter; Zhong, Guoneng; Emanuel, Beverly; Weissman, Sherman; Snyder, Michael; Gerstein, Marg (12 June 2007). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1891248">"Systematic prediction and validation of breakpoints associated with copy-number variations in the human genome"</a>. Proceedings of the National Academy of Sciences of the United States of America. 104 (24): 10110–5. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2007PNAS..10410110K">2007PNAS..10410110K</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1073%2Fpnas.0703834104">10.1073/pnas.0703834104</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1891248">1891248</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/17551006">17551006</a>.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li>A comprehensive review of HMM methods and software in bioinformatics – <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110304083408/http://bioinformatics.oxfordjournals.org/content/14/9/755.full.pdf">Profile Hidden Markov Models</a></li>

<li>Early HMM publications by Baum:

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20131005001241/http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.aoms%2F1177697196&page=record">A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20131004233805/http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.bams%2F1183528841&page=record">An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology</a></li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20131004233211/http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.aoms%2F1177699147&page=record">Statistical Inference for Probabilistic Functions of Finite State Markov Chains</a></li></ul></li>

<li>The Shannon Lecture by Welch, which speaks to how the algorithm can be implemented efficiently:

<ul><li><a rel="nofollow" class="external text" href="http://backup.itsoc.org/publications/nltr/it_dec_03final.pdf">Hidden Markov Models and the Baum–Welch Algorithm</a>, IEEE Information Theory Society Newsletter, Dec. 2003.</li></ul></li>

<li>An alternative to the Baum–Welch algorithm, the Viterbi Path Counting algorithm:

<ul><li>Davis, Richard I. A.; Lovell, Brian C.; <a rel="nofollow" class="external text" href="http://dl.acm.org/citation.cfm?id=1011682.1011688">"Comparing and evaluating HMM ensemble training algorithms using train and test and condition number criteria"</a>, Pattern Analysis and Applications, vol. 6, no. 4, pp. 327–336, 2003.</li></ul></li>

<li><a rel="nofollow" class="external text" href="http://www.cs.jhu.edu/~jason/papers/#eisner-2002-tnlp">An Interactive Spreadsheet for Teaching the Forward-Backward Algorithm</a> (spreadsheet and article with step-by-step walkthrough)</li>

<li><a rel="nofollow" class="external text" href="http://pandamatak.com/people/anand/771/html/node26.html">Formal derivation of the Baum–Welch algorithm</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120228202329/http://pandamatak.com/people/anand/771/html/node26.html">Archived</a> 2012-02-28 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li>

<li><a rel="nofollow" class="external text" href="http://www.kanungo.com/software/software.html#umdhmm">Implementation of the Baum–Welch algorithm</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-25" href="https://en.wikipedia.org/wiki/?title=Baum%E2%80%93Welch_algorithm&oldid=1297307363">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>